package crazy;

import java.io.BufferedWriter;
import java.io.FileOutputStream;
import java.io.OutputStreamWriter;

public class HeapSort
{
	private static String file =  "c:\\t.txt";
	
	public static void main(String[] args)
	{
		DataWrap[] data = {
				new DataWrap(9, ""),
				new DataWrap(79, ""),
				new DataWrap(46, ""),
				new DataWrap(30, ""),
				new DataWrap(58, ""),
				new DataWrap(49, "")}
				;
		System.out.println("befort--"+java.util.Arrays.toString(data));
		heapSort(data);
		System.out.println("after--"+java.util.Arrays.toString(data));
	}
	
	
	public static void heapSort(DataWrap[] data)
	{
		int arrayLength = data.length;
		for (int i = 0; i < arrayLength -1; i++)
		{
			builMaxHeap(data, arrayLength -1 -i);
			swap(data, 0, arrayLength - 1 - i);
			System.out.println(java.util.Arrays.toString(data));
		}
	}
	
	private static void builMaxHeap(DataWrap[] data, int lastIndex)
	{
		for (int i = (lastIndex -1)/2; i>=0; i--)
		{
			int k = i;
			while (k * 2+1<= lastIndex)//k*2+1是左节点。k*2+2是右节点
			{
				int biggerIndex = k*2 + 1;
				if (biggerIndex < lastIndex)
				{
					if (data[biggerIndex].compareTo(data[biggerIndex+1])<0)
					{
						biggerIndex++;
					}
				}
				if (data[k].compareTo(data[biggerIndex])<0)
				{
					swap(data, k, biggerIndex);
					k = biggerIndex;
				}
				else 
				{
					break;
				}
			}
		}
	}
	
	private static void swap(DataWrap[] data, int i, int j)
	{
		DataWrap tmp = data[i];
		data[i] = data[j];
		data[j] = tmp;
	}
	
	public static void writeLog(String file, String content)
	{
		BufferedWriter out = null;
		try
		{
			out = new BufferedWriter(new OutputStreamWriter(
					new FileOutputStream(file,true)));
			out.write(content+"\r\n");
			out.close();
		} catch (Exception e)
		{
			e.printStackTrace();
		}
	}
}
